Міністерство освіти і науки, молоді та спорту України
Національний університет „ Львівська політехніка ”
ІКТАМ
Кафедра ЕОМ
Курсова робота
з предмету:
“ Паралельні та розподілені обчислення ”
на тему:
“ Паралельне виконання операцій множення матриць ”
Завдання
Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче.
Визначення вхідних даних:
n1=2П = Е = 60
n2=3І = Д =104
n3=5Б =О = 333
5b-12b-6b-11b-8b-1b-3b-13b , де «nb»- номер букви П.І.Б.
ЕРНДОЧКІ=> 171,93,134,13,250,49,47,223
17110 = АВ16
9310 = 5D16
13410 = 8616
1310 = D16
25010 = FA16
4910 = 3116
472 = 2F16
22310 = DF16
Матриця зв’язків орієнтованого графу:
№проц.
1
2
3
4
5
6
7
8
1
0
0
1
0
1
0
1
1
2
0
0
0
1
1
1
0
1
3
1
0
0
0
0
1
1
0
4
0
0
0
0
1
1
0
1
5
1
1
1
1
0
0
1
0
6
0
0
1
1
0
0
0
1
7
0
0
1
0
1
1
0
1
8
1
1
0
1
1
1
1
0
Визначення початкового завантаження:
Номер залікової – 0909402
– спільна пам’ять.
Співвідношення часових параметрів:
, де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки.
tU – час виконання однієї операції множення;
tS – час виконання однієї операції сумування;
tP – час виконання однієї операції пересилання даних між процесорами;
tZ – час виконання операції завантаження одних даних;
tW – час виконання операції вивантаження одних даних.
Анотація
Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(60*104) та В(104*333) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю.
У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного.
Програма написана засобами мови C++ з використанням бібліотеки MPI.
Зміст
Завдання 2
Анотація 3
Вступ 5
1. Теоретичний розділ 6
2. Розробка блок-схеми виконання алгоритму 9
3. Розробка функціональної схеми 10
4. Розрахунковий розділ 11
5. Розробка програми 13
Висновки 15
Список літератури 16
Додаток А. Лістинг програми 17
Вступ
З розвитком комп’ютерної техніки все більше постає питання оптимального вирішення складних задач. Паралельні обчислення – один із методів, який дозволяє ефективно вирішувати певного виду задачі на багатопроцесорних системах, таких як прогноз погоди, задачі гідно- і газодинаміки, квантової хімії, біології і медицина, астрономії і багато інших. Множення матриць – також одна із таких задач.
Існує багато технологій реалізації паралельних обчислень, ефективність яких залежить переважно від параметрів системи: продуктивності комп’ютерів, розмірів і структури пам’яті, пропускної здатності каналів, використаних мов програмування, компіляторів, операційних систем та інших. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів і систем, що розподілені на великих територіях.
Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах.
У організації паралельних обчислень виникає низка проблем із синхронізацією роботи процесорів, рівномірним навантаженням системи, плануванням обчислень. В даній курсовій роботі буде проведено розробку алгоритму для вирішення задачі перемноженні двох матриць на кільцевій структурі.
Теоретичний розділ
Матриці та матричні операції широко використовуються при математичному моделюванні різноманітних процесів, явищ та систем. Матричні обчислення є основою великої кількості наукових та інженерних розрахунків серед прикладних об...
